package november.tree.threaded;


/**
 * @author huangxin
 * @date 2019/11/20-22:20
 * 线索化二叉树
 */
public class ThreadedBinaryTree {
    public static void main(String[] args) {
        ThreadedBinaryTree tree = new ThreadedBinaryTree();

        TreeNode root = new TreeNode(1, "root");
        root.left = new TreeNode(2, "abc");
        root.right = new TreeNode(3, "bcd");
        root.right.left = new TreeNode(5, "bcd");
        root.right.right = new TreeNode(4, "bcd");

        tree.root = root;


        //测试中序线索二叉树功能
        tree.threadedNodes();
        tree.threadedList();


    }

    public TreeNode root;

    /**
     * 在递归线索化时,pre总是指向前一个节点
     * 即当前节点的前驱节点
     */
    public TreeNode pre;

    /**
     * 线索化该节点
     */
    public void threadedNodes() {
        threadedNodes(this.root);
    }

    /**
     * 对当前节点进行线索化
     * @param node
     */
    public void threadedNodes(TreeNode node) {
        if (node == null) {
            return;
        }

        //判断左节点是不是指向子树,如果是,再线索化左子树
        //1.先线索化左子树
        threadedNodes(node.left);

        //2.线索化当前节点
        if (node.left == null) {
            //指向前驱节点
            node.left = pre;
            node.leftType = 1;
        }

        //3.线索化上一个节点pre的后继节点
        if (pre != null && pre.right == null) {
            //pre指向后继节点
            pre.right = node;
            pre.rightType = 1;
        }

        //处理完之后,让pre=当前节点
        pre = node;

        //再线索化右子树
        threadedNodes(node.right);
    }

    public void threadedList() {
        //临时变量,存储当前节点
        TreeNode temp = this.root;

        while (temp != null) {

//            循环找到leftType=1的节点
            while (temp.leftType == 0) {
                temp = temp.left;
            }

            //打印当前节点
            System.out.println(temp);

            while (temp.rightType == 1) {
                //如果当前节点的右侧指向的是后继节点,直接打印右侧节点
                temp = temp.right;
                System.out.println(temp);
            }
            temp = temp.right;

        }
    }

    //前序查找
    public TreeNode preSearch(int id) {
        if (this.root == null) {
            System.out.println("二叉树为空");
            return null;
        }
        return this.root.preSearch(id);
    }

    //中序查找
    public TreeNode infixSearch(int id) {
        if (this.root == null) {
            System.out.println("二叉树为空");
            return null;
        }
        return this.root.infixSearch(id);
    }

    //后序查找
    public TreeNode afterSearch(int id) {
        if (this.root == null) {
            System.out.println("二叉树为空");
            return null;
        }
        return this.root.afterSearch(id);
    }

    //删除
    public void delete(int id) {
        if (root != null) {
            //判断root节点
            if (root.id == id) {
                root = null;
            }
            root.delete(id);
        } else {
            System.err.println("无法删除空树");
        }
    }

}
